package com.leetcode.根据数据结构分类.链表;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2021/3/12
 * @description: 147. 对链表进行插入排序
 * https://leetcode-cn.com/problems/insertion-sort-list/
 * linkList 还是需要多画图鸭
 */
public class B_147_对链表进行插入排序 {

	static B_147_对链表进行插入排序 action = new B_147_对链表进行插入排序();

	public static void main(String[] args) {
		test1();
	}

	public static void test1() {
		ListNode head = new ListNode(4);
		head.next = new ListNode(2);
		head.next.next = new ListNode(1);
		head.next.next.next = new ListNode(3);
		ListNode res = action.insertionSortList(head);
		System.out.println("res = " + res);
	}

	public ListNode insertionSortList(ListNode head) {
		if (head == null) {
			return null;
		}
		//设置哨兵节点
		ListNode guard = new ListNode(0);
		guard.next = head;
		ListNode prev = guard;
		ListNode point = head;
		//cur 的 prev node
		ListNode curPrev = head;
		ListNode cur = head.next;

		while (cur != null) {
			while (cur.val > point.val) {
				prev = point;
				point = point.next;
			}
			//此时 cur.val <= point.val
			if (point == cur) {
				//如果是同一个节点，无须处理
				curPrev = cur;
				cur = cur.next;
			} else {
				//插入到 prev 后面
				ListNode temp = cur.next;
				prev.next = cur;
				cur.next = point;

				cur = temp;
				curPrev.next = cur;
			}
			prev = guard;
			point = guard.next;
		}

		return guard.next;
	}
}
